A problem of optimal routing in ATM networks is considered one of the most complex ones, since structure of such networks is characterized by a considerable number of limitations and parameters. In some cases the problem belongs to a so-called type of NP-problems, which are unsolvable.
There is a widely known system PNNI—Private Network-Network Interface—intended for use in ATM networks, which describes an accepted way for searching a path in the network according to values of standard parameters and limitations specified by a user for the path, wherein every link in the network is characterized by a number of standard parameters and limitations having respective particular values.
In ATM systems, routing usually comprises the following three steps:                applying to the network a so-called GCAC algorithm for preventing the use in the path of those links, which definitely do not satisfy one of the main parameters for limitations stated by the user (for example, the available Bandwidth), then        performing the procedure of path selection to allocate a path candidate,        checking whether the selected path candidate satisfies the requirements of the user (which also includes applying a so-called CAC algorithm for checking sufficient bandwidth); if the path does not satisfy the user's requirements, the path selection is repeated to find another path candidate, up to allocating a stable path,        
It should be noted that the step of GCAC is not mandatory, and its sorting functions may be performed after selecting the path candidate, etc.
The present invention relates to the procedure of path selection per se. Accuracy and optimality of the path selection were always considered important in the art of telecommunication. In the modem telecommunication world, transport networks become the most critical areas from the point of selecting the optimal path, since paths in such networks are usually selected for heavy traffic streams and for considerable time. It is therefore understood that in case when the telecommunication path selection determines both the quality conditions and the expenses for a long term, the selection result is highly responsible.
U.S. Pat. No. 5,933,421 describes a general algorithm of routing in ATM networks, including steps of updating a Topological Data Base, deleting non-applicable links after receiving a Reject for Setup, repeated path selection after receiving the Reject(s), etc. The patent mentions also a Path Selection method as being a component part of the general algorithm.
For the Path Selection, the following so-called QoS parameters are used—Available Cell Rate (ACR), Cell Transfer Delay (CTD), Cell Delay Variation (CDV), Cell loss Ratio (CLR). It should be noted that the mentioned parameters do not exactly correspond to definitions accepted in ATM.
According to the technique of U.S. Pat. No. 5,933,425, if a number of QoS parameters are specified by the connection request, the optimal path does not satisfy all of the requested QoS values simultaneously, since the attempt to do it would be an insolvable NP-problem. Therefore, the path selection in U.S. Pat. No. 5,933,425 is performed in a number of steps. In one or more variations of the method, a so-called Administrative Weight (AW) is used as a QoS parameter to calculate a sum of link costs for each of possible paths to destination in order to find an optimum path which gives a minimum value of the sums. This optimum path is further selected as a candidate using a QoS parameter requested by a user. Any selected QoS parameter is set into its evaluation function, or into a so-called link cost formula. The decision is made by steps, whether the path meets all the other requested QoS values. If any of the QoS requested parameters is not met, the path as reselected. However, the Path Selection technique, based on a single QoS parameter, requires a lot of computation time and, besides it, cannot always guarantee a successful path search. For example, a situation may be encountered where the required path exists but cannot be found using the described technique. Such a situation is typical for a network, in which some links have low values of CTD and large values of CDV while other links have large values of CTD and low values of CDV. It means that selection of a single parameter at each step leads to underestimation of other parameters' influence, which often cannot be corrected at the next step while definitely prolonging the path selection procedures.
To the best of the Inventor's knowledge, no methods of routing in ATM networks have been proposed to date which resolve the above-mentioned problem.